Caching is commonly used for improving computer performance when the system is frequently accessing objects which require significant time to fetch or create. By caching an object, the cost for fetching or creating the object is only incurred once. Subsequent requests for a cached object can then be satisfied from the cache, a process which incurs significantly less overhead than recalculating the object or fetching it from a remote location.
In many cases, caches are of finite size. Selectivity must be applied in determining which objects should be cached when the cache is full or almost full. The subject invention provides a method for determining which objects should be placed in a cache. It is particularly (but not exclusively) useful when multiple parameters affecting the desirability of caching objects vary for different objects. Such parameters include the frequency with which an object is accessed, object size, the time to calculate an object, or the time to fetch the object from a remote location, and the lifetime (i.e. time between updates) of an object.
Caching is particularly useful for improving performance in the World Wide Web. Several types of caching are currently being utilized to cache Web-retrieved objects which could make use of the present invention, including server caching, proxy caching and browser caching. Web server performance is often poor when the percentage of dynamic pages generated by the server is high (see "An Analysis of Web Server Performance" by A. Iyengar et. al., "Proceedings of GLOBECOM '97", November 1997). In order to improve performance, server caching of local dynamic data is utilized. In server caching, the server generating dynamic pages can cache dynamic pages so that they only have to be generated once (see "Improving Web Server Performance by Caching Dynamic Data", A. Iyengar and J. Challenger, "Proceedings of the Usenix Symposium on Internet Technologies and Systems", December 1997).
Another caching scheme is to have a proxy server cache documents from remote servers. Using proxy caching, the proxy server will be able to satisfy requests for documents without having to remotely fetch a document for each request (see "Caching Proxies: Limitations and Potentials" by M. Abrams et. al., "Fourth International World Wide Web Conference Proceedings", December 1996, pp. 119-133; and "World Wide Web Proxies" by A. Luotonen and K. Altis in "Computer Networks and ISDN Systems", vol. 27 (1994), pp. 147-154). Finally, browser caching is often used wherein web browsers cache recently requested documents and images both in main memory and on disk.
A number of cache replacement algorithms have been proposed in the literature (see "A Case for Delay-Conscious Caching of Web Documents", P. Scheuermann et. al., Sixth International World Wide Web Conference Proceedings, 1997; "Performance Engineering of the World Wide Web: Application to Dimensioning and Cache Design", J. Bolot and P. Hoschka, "World Wide Web Journal", Summer 1996, pp. 185-195; "Proxy Caching That Estimates Page Load Delays",R. P. Wooster and M. Abrams, "Sixth International World Wide Web Conference Proceedings", 1997; "Removal Policies in Network Caches for World-Wide Web Documents", S. Williams et. al., "Proceedings of SIGCOMM '96", pp. 293-305; "Intelligent Caching and Indexing Techniques for Relational Database Systems", T. Sellis, "Information Systems", vol. 13 no. 2, pp. 175-185, 1988.) Those set forth in the Bolot and Sellis references, utilize as parameters the time since an object was last referenced, the time to retrieve the item, the expected lifetime of the object, and the object size.
Commonly used methods for predicting the frequency with which an object is accessed include the time since the object was last accessed, in which the Least Recently Used (LRU) object is the candidate for replacement, and the LRU-K algorithm, discussed below. The time since the object was last accessed is one of the most common methods. It is of limited accuracy because it doesn't consider accesses before the most recent one. LRU-K, on the other hand, (see "The LRU-K Page Replacement Algorithm for Database Disk Buffering" by O'Neil et. al, in Proceedings of SIGMOD '93, pp. 297-306), estimates the time before the next access based on the time since the kth most recent access. LRU-K is equivalent to LRU when k=1. One drawback to LRU-K is that it weights the times between each of the last k references equally. A better strategy would be to assign more weight to more recent references. Another drawback to LRU-K is that the times of the last K references must be maintained for each object. The space overhead thus grows with K.
Some caching algorithms use a metric for the desirability of caching an object which is preferably proportional to the processing time which is saved by caching the object. Maintaining current values of the metric at all times as proposed in the prior art is, however, prohibitively expensive.
It is an objective of the present invention to provide a method for making caching decisions which balances the expense of caching with the benefits.